EVALUACIÓN PARCIAL

“El cálculo y el algoritmo son las dos ideas principales de la ciencia occidental” (David Berlinski)

“Las partes se derivan del todo y no el todo de las partes” (Arthur M. Young)

---

El Concepto de Evaluación Parcial
Introducción

La evaluación parcial es una técnica informática que consiste en la transformación de una expresión (básicamente, código fuente) mediante una especialización. Para ello, a la expresión original se le asignan valores a parte de sus parámetros y a continuación se evalúa, produciendo una nueva expresión, una expresión especializada.

Esta idea, simple pero poderosa, está tomada del área de las funciones matemáticas: una función curry es aquella en la que se aplica un sólo argumento cada vez, obteniéndose sucesivamente funciones cada vez más particularizadas con un parámetro menos.

La evaluación parcial es un mecanismo genérico que ha sido objeto de especial atención y estudio, pues aporta un paradigma unificador, una nueva perspectiva, en matemática, informática y lógica, habiendo recibido diferentes nombres: restricción, proyección, especialización y currificación (currying). Pero ha sido en programación el área donde más desarrollo ha experimentado, habiendo proporcionado además una ayuda muy valiosa para comprender las propiedades de los propios lenguajes de programación.


Motivación

La motivación principal de la evaluación parcial es aumentar la velocidad de ejecución, pues los programas particularizados son más eficientes que los programas genéricos. Existen, en este sentido, dos tendencias extremas:

1. Escribir muchos pequeños programas eficientes. La desventaja es que se necesita mucho esfuerzo de programación y de mantenimiento.
   
   
2. Escribir un sólo programa altamente parametrizado, capaz de resolver un amplio espectro de problemas. La desventaja es la ineficiencia, debido principalmente al proceso de los parámetros.

Lo mejor entre ambas posturas es escribir un programa altamente parametrizado y realizar evaluaciones parciales para obtener versiones más eficientes, comprensibles y manejables.


Proceso de evaluación parcial

La evaluación parcial puede se manual o automática. La especialización manual tiene el inconveniente de que es necesario realizar un esfuerzo de adaptación del código, con la consiguiente posible aparición de errores. Lo que más interesa es la evaluación parcial automática, por su comportamiento predecible y como mecanismo genérico:

Se parte de una expresión X (segmento de código fuente) parametrizada. El proceso de evaluación parcial automático consta de dos fases:

1. Fase de especialización.
   Se particulariza la expresión X asignando valores a algunos parámetros E (que se denominan “estáticos”) y se evalúa, obteniéndose una nueva expresión XX_EX (llamada “expresión especializada” o “residual”).
   
   La especialización automática implica el desarrollo de un evaluador parcial EP (o especializador): un programa (más bien, un metaprograma) con dos argumentos: el código fuente X y el conjunto E correspondiente a los parámetros estáticos. Su evaluación produce la expresión especializada X_E:
   
   
   EP(X, E) = X_E
   
   La expresión XE, en general, es más corta que la original (X), aunque a veces, por el despliegue de bucles o llamadas recursivas, podría ser más largo.
   
   
2. Fase de evaluación. Se asignan valores al resto de los parámetros D (que se denominan “dinámicos”) y se evalúa X_E con dichos parámetros dinámicos, es decir, XE(D), produciendo el resultado R:
   
   
   X_E(D) = R
   
   El resultado que se obtiene, R, es idéntico al que se obtendría evaluando X con todos los valores de los parámetros, es decir, X(E, D) = R.
   
   La expresión X_E(D) es más eficiente que X(_E, D), al haberse precomputado las partes de X que dependen sólo de E.

Tipos de evaluación parcial

El proceso de evaluación parcial puede ser de 3 tipos:

1. En línea (online). La fase de evaluación se realiza inmediatamente después de la fase de especialización, es decir, después de la obtención de la expresión especializada X_E.
   
   Su ventaja principal es que hace uso inmediato de los recursos computacionales, pero tiene el inconveniente de que la generación de código puede que no sea adecuado, incluso que sea infinito.
   
   
2. Fuera de línea (offline). La especialización se realiza en varias etapas. Inicialmente se realiza un preproceso de la expresión original (X) basado en la información sobre qué parámetros son estáticos, no en sus valores, y el especializador no realiza ningún proceso de decisión. En una segunda etapa, a partir de los valores concretos de los parámetros estáticos, tiene lugar el proceso de especialización (la obtención de X_E).
   
   Su ventaja principal es que permite la auto-aplicación (la aplicación al propio evaluador parcial EP) y la generación de generadores de programas. Además, el algoritmo de especialización es más simple.
   
   
3. Existe también la estrategia llamada mixline, en la que se mezclan los dos métodos anteriores.

Evaluación Parcial en MENTAL
En MENTAL la evaluación parcial es un mecanismo que está disponible directamente en el lenguaje. No se necesita desarrollar ningún programa especializador. Los recursos disponibles para realizar evaluaciones parciales son:

• Expresiones genéricas parametrizadas, mediante la asignación de valores a uno o varios parámetros.
  
  
• Expresiones del tipo x/y, en donde x es una expresión primaria e y es la expresión secundaria, que consiste en una o varias sustituciones. Se puede particularizar cualquier expresión (primaria), incluyendo datos, expresiones genéricas, etc. Es totalmente genérico, pues se aplica a todo tipo de expresiones. Ni siquiera es necesario que las expresiones tengan parámetros formales.
  
  
  • En la expresión secundaria se utilizan una o varias sustituciones (en serie o en paralelo) que afectan a la expresión primaria.
    
    
  • Una misma expresión primaria puede especializarse de diferentes formas, según la expresión secundaria que se aplique.
    
    
  • Una misma expresión secundaria puede aplicarse a diferentes expresiones primarias.

Una expresión especializada puede ser, a su vez, especializada (evaluación parcial de orden superior). En este caso, la evaluación parcial se puede considerar un tipo de proceso de evaluación por fases o etapas.

Combinado con el resto de las primitivas, se dispone de un entorno de gran flexibilidad y expresividad, incluyendo la posibilidad de evaluación en los tres modos (online, offline y mixline).


Ejemplos de particularización simple

1. 123/(3=a) // ev. 1a2
   
   
2. aaa/(a=123) // ev. (123 123 123)
   
   
3. (a*x + b*y + c)/(a=1 b=2) // ev. (x + 2*y + c)
   
   
4. (datos = (123 "pepe" 6.5))
datos/("pepe" = "juan") // ev. (123 "juan" 6.5)
datos/("pepe" = θ) // ev. (datos = (123 6.5))
   
   
5. ( z = ⟨( f(x y) = (x+y x*y) )⟩ )
z/(+° = −°) // ev. ⟨( f(x y) = (x−y x*y) )⟩

Ejemplos de currificación

1. Tenemos la función de dos argumentos
   
   ⟨( f(x y) = (x+y x*y) )⟩
   
   Una versión curry de f sería, por ejemplo, especializar el parámetro y con 7:
   
   ⟨( g(x) = f(x 7) )⟩ // ev. ⟨( g(x) = (x+7 x*7) )⟩
   
   Por lo tanto,
   
   g(2) // ev. (9 14)
g(a) // ev. (a+7 a*7)
   
   
2. Tenemos la función de unión (de secuencias o conjuntos).
   
   ⟨( union(x y) = (x↓ y↓) )⟩
   
   Si conocemos uno de los parámetros, p.e. y=(1 2 3), podemos especializar la expresión genérica:
   
   ⟨( union1(x) = union(x (1 2 3)) )⟩
   
   Esta expresión se evalúa como:
   ⟨( union1(x) = (x↓ 1 2 3) )⟩
   
   Ejemplos de aplicación:
   
   union1(a b c) // ev. (a b c 1 2 3)
union1(a b) // ev. (a b 1 2 3)
union1(a) // ev. (a 1 2 3)

Ejemplos de especialización de código

(c =: (x=5 ← a>b →' x=4)°

ce = c/(a=3 b=4) // ev. x=4 (código especializado)

ce // ev. x=4 (evaluación del código especializado)


Ejemplo de especialización de orden superior (especialización de especialización)

El producto escalar de dos secuencias numéricas x=(x1 … xn) e y=(y1 … yn) se define como la suma de los productos correspondientes a cada uno de los componentes de ambas secuencias:

⟨( pe(x y) = +⊢([(x\⌊i…x#⌋ * y\⌊1…y#⌋]) )⟩

Si conocemos que el tamaño de los vectores es 3, entonces podemos realizar la primera especialización:

⟨( (pe3((x1 x2 x3) (y1 y2 y3)) = pe((x1 x2 x3) (y1 y2 y3) )⟩

El resultado es:

⟨( (pe3((x1 x2 x3) (y1 y2 y3)) = (x1*y1 + x2*y2 + x3*y3) )⟩

Si conocemos ahora uno de los vectores, por ejemplo, y=(10 20 30), entonces tenemos una segunda especialización:

⟨( pe3a(x1 x2 x3) = (pe3((x1 x2 x3) (10 20 30)) )⟩

El resultado es:

⟨( pe3a(x1 x2 x3) = (10*x1 + 20*x20 + 30*x3) )⟩

Ejemplos de aplicación:

pe3a(1 2 3) // ev. (1*10 + 2*20 + 3*30) ev. 140
pe3a(1 1 1) // ev. (10 + 20 + 30) ev. 60

---

Adenda
Hitos en la historia de la evaluación parcial

• El término “curry” viene del lógico Haskell Brooks Curry, un investigador de lógica combinatoria, que aplicó esta técnica ampliamente en el área de las funciones recursivas [Curry, 1958, 1971]. La idea original fue de Moses Schönfinkel en 1924, pero fue Curry el primero en reconocer y sistematizar el trabajo de Schönfinkel.
  
  
• La posibilidad teórica de la evaluación parcial fue establecida en la teoría de las funciones recursivas mediante el teorema s-m-n de Kleene [1952].
  
  
• L.A. Lombardi [1967] fue probablemente el primero en utilizar el término “evaluación parcial” para referirse a computación con información incompleta, dentro del marco de la computación incremental con Lisp.
  
  
• Yoshihiko Futamura [1971] fue el primero en considerar que un evaluador parcial es un programa que podría aplicarse a sí mismo.
  
  
• Andrei Ershov [1982] usó el término “computación mixta”, pues un evaluador parcial produce una mezcla de ejecución y de generación de código.

Aplicaciones de la evaluación parcial

• Generación automática de programas. Especializando el programa generador y ejecutándolo, se obtienen diferentes programas. Es un tipo de metaprogramación [Jones y otros, 1993].
  
  
• Compiladores e intérpretes: generación de compiladores, compilación especializando un intérprete, etc. Se ha demostrado que la evaluación parcial está estrechamente ligada con la compilación [Futamura, 1971]. Es el área quizás más estudiada y en la que se han logrado más resultados.
  
  
• Generación de procesos paralelos especializados, especialmente para simulación.
  
  
• Informática gráfica. Por ejemplo, ray tracing (algoritmo para la síntesis de imágenes 3-D) con especialización de la escena a dibujar.
  
  
• Algoritmos de búsqueda en bases de datos. Los algoritmos altamente parametrizados consumen mucho tiempo analizando todos los argumentos, especialmente si éstos corresponden a objetos complejos.
  
  
• Programación genérica: desarrollo de programas reutilizables en diferentes contextos.
  
  
• Sistemas operativos. Para optimizar procesos.
  
  
• Reingeniería de software. La evaluación parcial permite descomponer programas grandes en otros más pequeños y más comprensibles.
  
  
• Implementación de lenguajes específicos de dominio a partir de lenguajes genéricos.

Aplicaciones avanzadas

• Evaluación parcial de un intérprete.
  
  Tenemos un lenguaje fuente L, un intérprete INT de ese lenguaje y un programa P escrito en el lenguaje L. Entonces se tiene:
  
  
  • La evaluación parcial (EP) del intérprete INT respecto al dato estático P (el programa) es el intérprete especializado INT_P:
    
    
    EP(INT, P) = INT_P
    
    Este tipo de especialización se llama “proyección de Futamura”.
    
    
  • La ejecución del intérprete INT con el dato estático P y el dato dinámico D es la misma que la ejecución del intérprete especializado con el dato dinámico D:
    
    
    INT(P, D)) = INT_P(D)
  
  
• Autoaplicación del especializador (especializar un especializador).
  
  Tenemos un lenguaje fuente L, un evaluador parcial (especializador) V implementado en un sublenguaje de L, y un programa P escrito en lenguaje L. Entonces se puede especializar el propio evaluador parcial V respecto al programa P:
  
  
  V(V, P) = V_P
  V(P, D) = V_P(D)
  
  V_P es, en este caso, un evaluador parcial especializado.

Bibliografía

• Bjorner, Dines.; Ershov, Andrei P.; Jones, Neil D., editors. Partial Evaluation and Mixed Computation. North-Holland, 1988.
  
  
• Curry, Haskell B.; Feys, Richard. Combinatory Logic, 1. North Holland, 1958.
  
  
• Curry, H.B.; Hindley, J.R.; Seldin, J. Combinatory Logic, 2. North-Holland, 1971.
  
  
• Danvy, O.; Glück, R.; Thieman, P., editors. Partial Evaluation. Lecture Notes in Computer Science, vol. 1110. Springer-Verlag, 1996.
  
  
• Ershov, A.P. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41-67, 1982.
  
  
• Futamura, Y. Partial evaluation of computing processs - an approach to a compiler-compiler. Systems, Computers, Controls, 2 (5): 45-50, 1971.
  
  
• Hatcliff, John; Mogensen, Torben Æ.; Thiemann, Peter, editors. Partial Evaluation: Practice and Theory. Lecture Notes in Computer Science, vol. 1706. Springer-Verlag, 1999.
  
  
• Jones, Neil D.; Gomard, Carsten K.; Sestoft, Peter. Partial Evaluation and Automatic Program Generation. Prentice Hall Series in Computer Science, 1993. Disponible online.
  
  
• Jorring, U. y Scherlis, W.L. Compilers and staging transformation. 13th ACM Symposium on Principles of Programming Languages, St. Petersburg, Florida, pp. 86-96, New York: ACM, 1986.
  
  
• Kleene, S.C. Introduction to Metamathematics. Van Nostrand, 1952.
  
  
• Lombardi, L.A. Incremental Computation. En F.L. Alt and M. Rubinoff (eds.) Advances in Computers, vol. 8, pp. 247-333, Academia Press, 1967.
  
  
• Partial-eval.org. Colección de recursos sobre evaluación parcial. http://partial-eval.org